// Created by WXX on 2021/10/4 10:26
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：40 ms, 在所有 C++ 提交中击败了26.99%的用户
 * 内存消耗：5.8 MB, 在所有 C++ 提交中击败了70.69%的用户
 */
class Solution {
public:

    static const int N = 50;
    int primes[N], cnt;
    bool st[N];

    void init(int n) {
        st[1] = true;
        for (int i = 2; i <= n; i++) {
            if (!st[i]) primes[cnt++] = i;
            for (int j = 0; primes[j] * i <= n; j++) {
                st[primes[j] * i] = true;
                if (i % primes[j] == 0) break;
            }
        }
    }

    int countPrimeSetBits(int left, int right) {
        init(N - 1);

        int res = 0;
        for (int i = left; i <= right; i++) {
            int cnt = 0;
            for (int j = 0; j <= 31; j++)
                if (i >> j & 1)
                    cnt++;
            res += !st[cnt];
        }
        return res;
    }
};

int main() {

    cout << Solution().countPrimeSetBits(6, 10) << endl;  // 4

    return 0;
}
